//
//  GraphMatrix.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/15.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

/// 基于邻接矩阵实现的图结构
public final class GraphMatrix<V, E>: Graph<V, E> {
    
    /// 顶点集
    var vertexes: Vector<Vertex<V>> // n
    /// 边集
    var edges: Vector<Vector<Edge<E>?>> // n * n
    
    override init() {
        vertexes = []
        edges = []
    }
    
    /// 顶点操作
    // 插入顶点会使得矩阵的规模发生变化
    override func insert(_ v: V) -> Int {
        // 1: 边集的每一列都扩充一个单位
        for j in 0..<n { edges[j].insert(nil) }
        n += 1 // 规模增加
        // 2: 边集扩充一行
        let lastRow = Vector<Edge<E>?>(capacity: n)
        for _ in 0..<n { lastRow.insert(nil) }
        edges.insert(lastRow)
        // 3: 插入新顶点
        vertexes.insert(Vertex(v))
        // 返回插入位置
        return n - 1
    }
    
    override func remove(at index: Int) -> V {
        // 删除所有的出边
        for j in 0..<n {
            // 删除边不用判断是否存在 但是减少入度需要
            if exists(at: index, relativeTo: j) {
                edges[index].remove(at: j)
                vertexes[j].inDegree -= 1
            }
        }
        // 删除第index行
        edges.remove(at: index)
        n -= 1
        // 删除所有的入边
        for j in 0..<n {
            if exists(at: j, relativeTo: index) {
                edges[j].remove(at: index)
                vertexes[j].outDegree -= 1

            }
        }
        // 删除位于index顶点
        let vertexData = vertexes[index].data
        vertexes.remove(at: index)
        return vertexData
    }
    
    /// 需要保证vertexes[index]确实存在
    override func vertex(at index: Int) -> V {
        return vertexes[index].data
    }
    
    override func inDegree(at index: Int) -> Int {
        return vertexes[index].inDegree
    }
    
    override func outDegree(at index: Int) -> Int {
        return vertexes[index].outDegree
    }
    
    override func status(at index: Int) -> VStatus {
        return vertexes[index].status
    }
    
    override func dTime(at index: Int) -> Int {
        return vertexes[index].dTime
    }
    
    override func fTime(at index: Int) -> Int {
        return vertexes[index].fTime
    }
    
    override func parent(at index: Int) -> Int {
        return vertexes[index].parent
    }
    
    override func priority(at index: Int) -> Int {
        return vertexes[index].priority
    }
    
    // 若已枚举至邻居otherIndex，则转向下一个邻居
    override func nextNbr(at index: Int, relativeTo otherIndex: Int) -> Int {
        var otherIndex = otherIndex
        // index位置上的顶点的邻接顶点存在当且仅当其所在行数值为1
        // 逆向查找直至otherIndex越过vector的左边界结束
        while (otherIndex > -1) && !exists(at: index, relativeTo: otherIndex) {
            otherIndex -= 1
        }
        return otherIndex
    }
    
    override func firstNbr(at index: Int) -> Int {
        // 假想位置为n的顶点与所有顶点相邻
        // 尽管顶点为n的顶点都不存在
        return nextNbr(at: index, relativeTo: n)
    }
    
    
    /// 边操作(矩阵的规模并不会因此发生变化)
    override func exists(at index: Int, relativeTo otherIndex: Int) -> Bool {
        // 验证边是否存在只需要判定下标是否合法 && 下标所指示的位置是否有元素存在
        let idxValidation = index >= 0 && index < n && otherIndex >= 0 && otherIndex < n
        return idxValidation && edges[index][otherIndex] != nil
    }
    
    override func insert(_ d: E, _ w: Int, at index: Int, relativeTo otherIndex: Int) {
        // 忽略已有的边
        if exists(at: index, relativeTo: otherIndex) { return }
        // 给位于index和otherIndex的两个顶点记录边
        let edge = Edge(d, w)
        edges[index][otherIndex] = edge
        // 边数增加
        e += 1
        // 更新位于index的顶点的出度
        vertexes[index].outDegree += 1
        // 更新位于otherIndex的顶点的入度
        vertexes[otherIndex].inDegree += 1
    }
    
    // 需确定边存在
    override func remove(at index: Int, relativeTo otherIndex: Int) -> E {
        // 删除边
        let edgeData = edges[index][otherIndex]!.data
        edges[index][otherIndex] = nil
        // 边数减少
        e -= 1
        // 更新位于index的顶点的出度
        vertexes[index].outDegree -= 1
        // 更新位于otherIndex的顶点的入度
        vertexes[otherIndex].inDegree -= 1
        // 返回对于的边信息
        return edgeData
    }
    
    // 必须保证下标有效性
    override func type(at index: Int, relativeTo otherIndex: Int) -> EType {
        return edges[index][otherIndex]!.type
    }
    
    override func weight(at index: Int, relativeTo otherIndex: Int) -> Int {
        return edges[index][otherIndex]!.weight
    }
    
    override func edge(at index: Int, relativeTo otherIndex: Int) -> E {
        return edges[index][otherIndex]!.data
    }
}
